/*
检查条件1 Mp.size() - mp.size() > 1
if true move Mp.top to mp.top
else nothing

condition2: if x < Mp.top  insert into Mp
if x>Mp.top insert x into mp
check condition1

初始插入到最大堆
5 2 1 3 4
Mp 1 2
mp 5

if len(max_heap) > len(min_heap) + 1:
    移动max_heap顶到min_heap
elif len(min_heap) > len(max_heap):
    移动min_heap顶到max_heap
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

#define lld long long // long long 的printf 占位符是lld
#define ENDL '\n'     // 将 endl 替换为 \n 取消缓冲区
#define mod %
const lld N = 1e5 + 9;
const lld MOD_N = 1e9 + 7;
const lld MAX_ = 1e9;

using std::cin;
using std::cout;
using std::priority_queue;
using std::queue;
using std::set;
using std::stack;
using std::string;
using std::unordered_set;
using std::vector;
int a[10009];
lld sum = 0;
int find(int num[], int L, int R) {
  // 返回中位数
  if (L == R)
    return L;
  int n = R - L + 1;
  vector<int> temp(num + L, num + R + 1);
  std::sort(temp.begin(), temp.end());

  int mid = temp[n / 2];
  for (int i = L; i <= R; ++i) {
    if (num[i] == mid)
      return i;
  }
}
void dfs(int L, int R, int d) {
  if (L > R)
    return;

  int mid = find(a, L, R);
  // cout << "a[mid]=" << a[mid] << " "<< "d=" << d << ENDL;
  sum += (lld)a[mid] * d;

  dfs(L, mid - 1, d + 1);
  dfs(mid + 1, R, d + 1);
}
void solve() {
  // body
  memset(a, 0, sizeof(a));
  sum = 0;
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> a[i];
  dfs(1, n, 1);
  cout << sum << ENDL;
}
int main() {
  int T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
}
/*
5
1
1
2
1 2
5
5 2 1 3 4
5
1 5 2 4 3
5
3 4 2 5 1

1
4
33
42
42
*/